/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序（Merge Sort）是建立在归并操作上的一种有效的稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * <p>
 * 归并排序过程分为三步：
 * <p>
 * （1）分解。将 n 个元素分层各含 n/2 个元素的子序列。
 * <p>
 * （2）求解。用归并排序对两个子序列递归地排序。
 * <p>
 * （3）合并。合并两个已经排好序的子序列以得到排序结果。
 *
 * 归并排序时间复杂度为 O(nlog₂n)。
 *
 * <a href="https://www.dotcpp.com/course/896">课程地址</a>
 *
 * @author lizhixing
 */
public class MergeSort {

  public static void main(String[] args) {
    int[] arr = new int[] { 86, 23, 7, 45, 19, 10 };
    int left = 0;
    int right = arr.length - 1;
    int[] tem = Arrays.copyOf(arr, arr.length);
    print(arr);
    mergeSort(arr, left, right, tem);
    print(arr);
  }

  public static void mergeSort(int[] arr, int left, int right, int[] tem) {
    if (right - left < 1) {
      return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, tem);
    mergeSort(arr, mid + 1, right, tem);
    merge(arr, left, mid, right, tem);
  }

  private static void merge(int[] arr, int left, int mid, int right, int[] tem) {
    int index = 0;
    int l = left, r = mid + 1;
    while (l <= mid && r <= right) {
      if (arr[l] < arr[r]) {
        tem[index++] = arr[l++];
      } else {
        tem[index++] = arr[r++];
      }
    }
    while (l <= mid) {
      tem[index++] = arr[l++];
    }
    while (r <= right) {
      tem[index++] = arr[r++];
    }
    for (int i = 0; i < (right - left + 1); i++) {
      arr[left + i] = tem[i];
    }
  }

  private static void print(int[] arr) {
    for (int i : arr) {
      System.out.print(i + "\t");
    }
    System.out.println();
  }

}
